The present invention relates to an forward error correction system, and in particular, relates to such a system which encodes an information sequence using a convolutional code at the transmitting end and decodes such a sequence using sequential decoding at the receiving end.
A forward error correction (FEC) has been known as an efficient technique for removing channel errors.
There exists two major types of the code which are used for a forward error correction system. One is a block code, and the other is a convolutional code.
A block code system separates a series of information data into blocks, each of which is encoded according to a predetermined algorithm. A block code is now used mainly in the audio, video, and computer field.
In a convolutional code, information bits are encoded continuously by using shift registers and Exclusive-OR circuits, and it is used in particular in satellite communications. The present invention relates to the decoding of a convolutional code.
A convolutional code can be decoded either by
Viterbi decoding or sequential decoding. The Viterbi decoding provides the maximum likelihood decoding, which attains the largest coding gain under the given constraint length. However, the Viterbi decoding has the disadvantage that the decoding complexity grows exponentially with its constraint length, so that it is difficult to decode a code with a long constraint length.
In this case, sequential decoding is used.
In sequential decoding, a tree structure of the convolutional code is used for searching a path which is considered to be the most likely locally. The decoding complexity is rather insensitive to the code constraint length, and so codes with a long constraint length are often used and can be decoded rather easily in the sequential decoding. When the channel becomes noisy, it must search many branches to find out the correct path, and so, substantial decoding effort is required. In other words, the condition of the channel affects the decoding complexity. Two well-known decoding algorithms for sequential decoding are a Fano algorithm and a stack algorithm.
In a Fano algorithm, a search pointer moves forward and backward for finding out a correct path. However, when the error rate becomes high, the number of computations for finding out a correct path increases exponentially. In this case, a search pointer sometimes goes back so far that it violates the backsearch limit, and when this happens, the decoder is considered to have reached the overflow point, and is initialized.
In the stack algorithm, a number of nodes stored in a stack memory also increases when the error rate becomes high. When that number exceeds the stack memory capacity, the stack overflow occurs, and a further path search is impossible.
As described above, a prior art sequential decoding system has the disadvantage that it takes a lot of decoding effort when in a noisy channel so that it may degrade the total bit error performance even though it can decode a convolutional code with a long constraint length.